/*
    例题：现在有1元硬币1个 2元硬币2个 5元硬币3个 求能组成的数额和方案数
    母函数：G(x)=(1+x^1)*(1+x^2+x^4)*(1+x^5+x^10+x^15)       这里的1其实是x^0
    =x^20+x^19+x^18+x^17+x^16+2*x^15+...+x^3+x^2+x+1
    x^20表示可以凑成20元 方案数即为系数1 {5,5,5,2,2,1}
    因此模板的主要内容就是多项式的乘法
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=10050;
//数组保存多项式系数
int tmp[MAXN];
int ans[MAXN];
int main(void){
    //a b c分别表示1 2 5元硬币的个数
    int a=1;
    int b=2;
    int c=3;
    memset(tmp,0,sizeof(tmp));
    memset(ans,0,sizeof(ans));
    //a b c也可以初始化为数组 用三重循环实现

    //初始化第一个多项式
    for(int i=0;i<=a;i++){
        ans[i]=1;
    }
    //第一和第二个多项式相乘
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            tmp[i+2*j]+=ans[i];
        }
    }
    for(int i=0;i<=(a+2*b);i++){
        ans[i]=tmp[i];
        tmp[i]=0;
    }
    //第二和第三个多项式相乘
    for(int i=0;i<=(a+2*b);i++){
        for(int j=0;j<=c;j++){
            tmp[i+5*j]+=ans[i];
        }
    }
    for(int i=0;i<=(a+2*b+5*c);i++){
        ans[i]=tmp[i];
        tmp[i]=0;
    }
    //注意这里要+1
    for(int i=0;i<=(a+2*b+5*c+1);i++){
        if(ans[i]==0){
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}
